W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Approximation of a real function by another function is a task of finding such real function that has certain properties and can be used instead of with relatively small error. Most often is expected to be simpler than in some way and it should be possible to compute its values efficiently.
We define a staircase function as a real function such that its domain can be partitioned into intervals of the form (with and being some real numbers) satisfying the property that is constant on each of these intervals. Such interval for which is constant is called a stair of the function.
For simplicity let us assume that considered functions can change values only in points with integer -coordinate (so they are constant on any interval of the form where is an integer) and the domain we are interested in is .
We are interested in approximation of a staircase function which has at most stairs by functions having at most stairs. The error of approximation that we are willing to minimize is defined as:
for some value of the parameter .
Write a program which:
The first line of the input file contains three integers , and (, , ), separated with single spaces. denotes the number of stairs of function whereas denotes the maximum number of stairs of function . Each of the following lines contains one integer () - the value of at all points from the interval , where .
Remark: tests with different values of are not grouped together.
The first and only line of the output file should contain one non-negative real number - the error of the best approximation of by any -stair function . The difference between the actual answer and your program's answer must not be greater than .
For the input data:
6 3 1 0 3 3 2 9 0
the correct result is:
4.00
(for the correct answer would be ).
Task author: Krzysztof Duleba.